@SuppressWarnings("unchecked")
public class ArrayList<E> extends AbstractList<E> {
  
  private static final int DEFAULT_CAPATICY = 2;

  // 所有元素
  private E[] elements;

  public ArrayList(int capaticy) {
    capaticy = (capaticy < DEFAULT_CAPATICY) ? DEFAULT_CAPATICY : capaticy;
    elements = (E[]) new Object[capaticy];
  }

  public ArrayList() {
    this(DEFAULT_CAPATICY);
  }

  // 清楚所有元素
  public void clear() {
    for (int i = 0; i < size; i++) {
      elements[i] = null;
    }
    size = 0;
  }

  public void add (int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacity(size + 1);

    for (int i = size - 1; i >= index; i--) {
      elements[i + 1] = elements[i];
    }
    elements[index] = element;
    size ++;
  }

  // 获取index位置的元素 
  public E get(int index) {
    rangeCheck(index);
    return elements[index];
  }

  // 设置index位置的元素
  public E set(int index, E element) {
    rangeCheck(index);
    E old = elements[index];
    elements[index] = element;
    return old;
  }

  // 删除index位置元素
  public E remove(int index) {
    E old = get(index);
    int lastIndex = size - 1;
    if (index <= lastIndex) {
      for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
      }
    }
    elements[lastIndex] = null;
    size --;
    return old;
  }

  public int indexOf(E element) {
    for (int i = 0; i < size; i++) {
      if (elements[i] == element) return i;
    }
    return ELEMENT_NOT_FOUND;
  }

  // 保证要有 capacity 的容量
  private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;

    // OC 系数为 1.6
    // Java 系数 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新容量为旧容量 的 1.5倍。位移的小数处理 精度比较高(java浮点运算有精准度问题)

    // int newCapacity = oldCapacity << 1; // 2倍
    E[] newElement = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
      newElement[i] = elements[i];
    }
    elements = newElement;
    System.out.println("扩容：" + oldCapacity + "_ 扩容为" + newCapacity);
  }

  @Override
  public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(", [\n");

    for (int i = 0; i < size; i++) {
      if (i != 0) { // 1
        string.append(", \n");
      }
      string.append("  ");
      string.append(elements[i]);

      // if (i != size - 1) { // 2 : 有一个减法的操作，不如1好
      //   string.append(", ");
      // }
    }

    string.append("\n]");
    return string.toString();
  }
}